﻿#include<iostream>
#include<vector>
#include <algorithm>
#include <unordered_set>
#include<set>
using namespace std;

int bitsum(int n)
{
	int sum = 0;
	while (n >= 10)
	{
		int dest = n % 10;
		n /= 10;
		sum += dest * dest;
	}
	sum += n * n;
	return sum;
}

//力扣原题:快乐数 https://leetcode.cn/problems/happy-number/submissions/610594421/

/*
解法一：集合检测法
思路解析：
	该方法利用集合（set）来记录计算过程中出现的所有平方和。每次计算新的平方和，
	若结果为1则返回true；若该结果已存在于集合中，说明进入循环，返回false；否则将结果加入集合继续循环。

核心步骤：

	初始化一个集合用于记录出现过的数值。

	循环计算平方和：
		若平方和为1，返回true。
		若平方和已存在于集合，说明进入循环，返回false。
		否则将平方和加入集合并更新当前数值。

时间复杂度： O(k)，其中k为到达1或检测到循环所需的步数。
空间复杂度： O(k)，需存储所有出现过的数值。
*/

/*解法二：快慢指针法
思路解析：
	借鉴链表环检测的思想，使用两个指针：慢指针每次计算一次平方和，快指针计算两次
	。若存在循环，两指针终会相遇。相遇后判断是否为1即可确定结果。

核心步骤：

	初始化慢指针slow = n，快指针fast = bitsum(n)。

	循环移动指针直到相遇：
		慢指针移动一步：slow = bitsum(slow)。
		快指针移动两步：fast = bitsum(bitsum(fast))。

相遇后，检查当前值是否为1，若是则为快乐数，否则不是。
*/



int main()
{

	//除模做法
	int n;
	cin >> n;
	set<int> record;
	bool ret = false;
	
	while(!ret)
	{
		int sum = 0;
		while(n>=10)
		{
			int dest = n % 10;
			n /= 10;
			sum += dest * dest;
		}
		sum += n * n;
		if (sum==1)
		{
			ret = true;
		}
		else
		{

			auto flag= record.insert(sum);//插入失败表示有重复数
			if (!flag.second)
			{
				break;
			}
			n = sum;
		}
	}
	cout << ret;

	//快慢指针做法
	int slow = n, fast = bitsum(n);
	while(slow!=fast)
	{
		slow = bitsum(slow);
		fast = bitsum(bitsum(fast));
	}



	return 0;
}
